home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / BYacc-CW 1.9 / closure.c < prev    next >
C/C++ Source or Header  |  1995-05-20  |  4KB  |  254 lines
  1. #include "defs.h"
  2.  
  3. short *itemset;
  4. short *itemsetend;
  5. unsigned *ruleset;
  6.  
  7. static unsigned *first_derives;
  8. static unsigned *EFF;
  9.  
  10.  
  11. static void set_EFF(void)
  12. {
  13.     register unsigned *row;
  14.     register int symbol;
  15.     register short *sp;
  16.     register int rowsize;
  17.     register int i;
  18.     register int rule;
  19.  
  20.     rowsize = WORDSIZE(nvars);
  21.     EFF = NEW2(nvars * rowsize, unsigned);
  22.  
  23.     row = EFF;
  24.     for (i = start_symbol; i < nsyms; i++)
  25.     {
  26.     sp = derives[i];
  27.     for (rule = *sp; rule > 0; rule = *++sp)
  28.     {
  29.         symbol = ritem[rrhs[rule]];
  30.         if (ISVAR(symbol))
  31.         {
  32.         symbol -= start_symbol;
  33.         SETBIT(row, symbol);
  34.         }
  35.     }
  36.     row += rowsize;
  37.     }
  38.  
  39.     reflexive_transitive_closure(EFF, nvars);
  40.  
  41. #ifdef    DEBUG
  42.     print_EFF();
  43. #endif
  44. }
  45.  
  46.  
  47. void set_first_derives(void)
  48. {
  49.     register unsigned *rrow;
  50.     register unsigned *vrow;
  51.     register int j;
  52.     register unsigned k;
  53.     register unsigned cword;
  54.     register short *rp;
  55.  
  56.     int rule;
  57.     int i;
  58.     int rulesetsize;
  59.     int varsetsize;
  60.  
  61.     rulesetsize = WORDSIZE(nrules);
  62.     varsetsize = WORDSIZE(nvars);
  63.     first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  64.  
  65.     set_EFF();
  66.  
  67.     rrow = first_derives + ntokens * rulesetsize;
  68.     for (i = start_symbol; i < nsyms; i++)
  69.     {
  70.     vrow = EFF + ((i - ntokens) * varsetsize);
  71.     k = BITS_PER_WORD;
  72.     for (j = start_symbol; j < nsyms; k++, j++)
  73.     {
  74.         if (k >= BITS_PER_WORD)
  75.         {
  76.         cword = *vrow++;
  77.         k = 0;
  78.         }
  79.  
  80.         if (cword & (1 << k))
  81.         {
  82.         rp = derives[j];
  83.         while ((rule = *rp++) >= 0)
  84.         {
  85.             SETBIT(rrow, rule);
  86.         }
  87.         }
  88.     }
  89.  
  90.     vrow += varsetsize;
  91.     rrow += rulesetsize;
  92.     }
  93.  
  94. #ifdef    DEBUG
  95.     print_first_derives();
  96. #endif
  97.  
  98.     FREE(EFF);
  99. }
  100.  
  101.  
  102. void closure(short *nucleus, int n)
  103. {
  104.     register int ruleno;
  105.     register unsigned word;
  106.     register unsigned i;
  107.     register short *csp;
  108.     register unsigned *dsp;
  109.     register unsigned *rsp;
  110.     register int rulesetsize;
  111.  
  112.     short *csend;
  113.     unsigned *rsend;
  114.     int symbol;
  115.     int itemno;
  116.  
  117.     rulesetsize = WORDSIZE(nrules);
  118.     rsp = ruleset;
  119.     rsend = ruleset + rulesetsize;
  120.     for (rsp = ruleset; rsp < rsend; rsp++)
  121.     *rsp = 0;
  122.  
  123.     csend = nucleus + n;
  124.     for (csp = nucleus; csp < csend; ++csp)
  125.     {
  126.     symbol = ritem[*csp];
  127.     if (ISVAR(symbol))
  128.     {
  129.         dsp = first_derives + symbol * rulesetsize;
  130.         rsp = ruleset;
  131.         while (rsp < rsend)
  132.         *rsp++ |= *dsp++;
  133.     }
  134.     }
  135.  
  136.     ruleno = 0;
  137.     itemsetend = itemset;
  138.     csp = nucleus;
  139.     for (rsp = ruleset; rsp < rsend; ++rsp)
  140.     {
  141.     word = *rsp;
  142.     if (word)
  143.     {
  144.         for (i = 0; i < BITS_PER_WORD; ++i)
  145.         {
  146.         if (word & (1 << i))
  147.         {
  148.             itemno = rrhs[ruleno+i];
  149.             while (csp < csend && *csp < itemno)
  150.             *itemsetend++ = *csp++;
  151.             *itemsetend++ = itemno;
  152.             while (csp < csend && *csp == itemno)
  153.             ++csp;
  154.         }
  155.         }
  156.     }
  157.     ruleno += BITS_PER_WORD;
  158.     }
  159.  
  160.     while (csp < csend)
  161.     *itemsetend++ = *csp++;
  162.  
  163. #ifdef    DEBUG
  164.   print_closure(n);
  165. #endif
  166. }
  167.  
  168.  
  169.  
  170. void finalize_closure(void)
  171. {
  172.   FREE(itemset);
  173.   FREE(ruleset);
  174.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  175. }
  176.  
  177.  
  178. #ifdef    DEBUG
  179.  
  180. static void print_closure(n)
  181. int n;
  182. {
  183.   register short *isp;
  184.  
  185.   printf("\n\nn = %d\n\n", n);
  186.   for (isp = itemset; isp < itemsetend; isp++)
  187.     printf("   %d\n", *isp);
  188. }
  189.  
  190.  
  191. print_EFF(void)
  192. {
  193.     register int i, j;
  194.     register unsigned *rowp;
  195.     register unsigned word;
  196.     register unsigned k;
  197.  
  198.     printf("\n\nEpsilon Free Firsts\n");
  199.  
  200.     for (i = start_symbol; i < nsyms; i++)
  201.     {
  202.     printf("\n%s", symbol_name[i]);
  203.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  204.     word = *rowp++;
  205.  
  206.     k = BITS_PER_WORD;
  207.     for (j = 0; j < nvars; k++, j++)
  208.     {
  209.         if (k >= BITS_PER_WORD)
  210.         {
  211.         word = *rowp++;
  212.         k = 0;
  213.         }
  214.  
  215.         if (word & (1 << k))
  216.         printf("  %s", symbol_name[start_symbol + j]);
  217.     }
  218.     }
  219. }
  220.  
  221.  
  222. print_first_derives(void)
  223. {
  224.     register int i;
  225.     register int j;
  226.     register unsigned *rp;
  227.     register unsigned cword;
  228.     register unsigned k;
  229.  
  230.     printf("\n\n\nFirst Derives\n");
  231.  
  232.     for (i = start_symbol; i < nsyms; i++)
  233.     {
  234.     printf("\n%s derives\n", symbol_name[i]);
  235.     rp = first_derives + i * WORDSIZE(nrules);
  236.     k = BITS_PER_WORD;
  237.     for (j = 0; j <= nrules; k++, j++)
  238.         {
  239.       if (k >= BITS_PER_WORD)
  240.       {
  241.           cword = *rp++;
  242.           k = 0;
  243.       }
  244.  
  245.       if (cword & (1 << k))
  246.         printf("   %d\n", j);
  247.     }
  248.     }
  249.  
  250.   fflush(stdout);
  251. }
  252.  
  253. #endif
  254.